# 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
#  对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
#
#  你可以返回任何满足上述条件的数组作为答案。
#
#  示例：
#  输入：[4,2,5,7]
# 输出：[4,5,2,7]
# 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
from typing import List


class Solution:
    def sortArrayByParityII2(self, nums: List[int]) -> List[int]:
        """
        双指针
        为数组的偶数下标部分和奇数下标部分分别维护指针 i,j。
        遍历数组 如果 nums[i]为奇数，则不断地向前移动j（每次移动两个单位），直到遇见下一个偶数。 此时，可以直接将 nums[i]与 nums[j]交换。
        :param nums:
        :return:
        """
        even, odd = 0, 1
        while even < len(nums):
            if nums[even] % 2 == 1:
                while odd < len(nums) and nums[odd] % 2 == 1:
                    odd += 2

                nums[odd], nums[even] = nums[even], nums[odd]
            even += 2

        return nums

    def sortArrayByParityII1(self, nums: List[int]) -> List[int]:
        res = nums.copy()
        even, i, odd, = 0, 0, 1
        while i < len(nums):
            if nums[i] % 2 == 0:
                res[even] = nums[i]
                even += 2
            else:
                res[odd] = nums[i]
                odd += 2
            i += 1
        return res

    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        return self.sortArrayByParityII2(nums)


if __name__ == "__main__":
    nums = [4, 2, 5, 7, 9, 10]
    # nums[3], nums[2] = nums[2], nums[3]
    print(nums)
    print(Solution().sortArrayByParityII(nums))
